package algorithms

//求逆序数
func reversePairs(nums []int) int {
	res := 0
	mergeSortCounting(nums, 0, len(nums)-1,&res)
	return res
}
func mergeSortCounting(a []int, p, r int,res *int) {
	//终结条件
	if p >= r {
		return
	}
	var q = (p + r) / 2
	//divide and conquer,recursion
	mergeSortCounting(a, p, q,res)
	mergeSortCounting(a, q+1, r,res)
	//在merge统计逆序数
	merge(a, p, q, r,res)
}

func merge(a []int, p, q, r int,res *int) {
	//i遍历左，j遍历右，k遍历tmp
	var i, j, k = p, q + 1, 0
	tmp := make([]int, r-p+1)
	for i <= q && j <= r {
		if a[i] <= a[j] {
			tmp[k] = a[i]
			k++
			i++
		} else {
			*res += q - i + 1 // 统计p-q之间，比a[j]大的元素个数
			tmp[k] = a[j]
			k++
			j++
		}
	}
	for i <= q{ // 处理剩下的
		tmp[k] = a[i]
		k++
		i++
	}
	for j <= r { // 处理剩下的
		tmp[k] = a[j]
		k++
		j++
	}
	for i := 0; i < r-p+1; i++ { // 从tmp拷贝回a
		a[p+i] = tmp[i]
	}
}
//53. 最大子数组和
func maxSubArray(nums []int) int {
	n:=len(nums)

	var max= func(a,b,c int)int {
		if a>b{
			if a>c{
				return a
			}
			return c
		}
		if b>c{
			return b
		}
		return c
	}

	var mergeMiddle =func(low,high,mid int)int{
		max:=nums[mid]
		sum:=nums[mid]
		for i:=mid-1;i>=low;i--{
			sum+=nums[i]
			if sum>max{
				max=sum
			}
		}

		sum=max
		for i:=mid+1;i<=high;i++{
			sum+=nums[i]
			if sum>max{
				max=sum
			}
		}
		return max
	}

	var merge func(int,int)int
	merge= func(i, j int) int{
		if i>=j{
			return nums[i]
		}
		mid:=i+(j-i)>>1
		a:=merge(i,mid-1)
		b:=merge(mid+1,j)
		c:=mergeMiddle(i,j,mid)
		return max(a,b,c)
	}
	return merge(0,n-1)
}
